package com.fengkai.filepost.pdfoutstream.test.ODsolutions;

/**
 * @author Fengkai
 * @creat 2023/4/13
 * 向一个空栈中依次存入正整数
 * 假设入栈元素N(1 <= N <= 2^31-1)
 * 按顺序依次为Nx ... N4、N3、N2、N1,
 * 当元素入栈时，如果N1=N2+...Ny (y的范围[2,x],1 <= x <= 1000)
 * 则N1到Ny全部元素出栈,重新入栈新元素M(M=2*N1)
 * 如依次向栈存储6、1、2、3,当存储6、1、2时
 * 栈底至栈顶以此为[6、1、2]:当存入3时，3=2+1,
 * 3、2、1全部出栈，重新入栈元素6，(6=2*3)此时栈中有元素6
 * 因为6=6,所有两个六全部出栈存入12
 * 最终栈中只剩一个元素12
 * a 输入
 * 使用单个空格隔开的正整数的字符串
 * 如：5 6 7 8,左边的数字先入栈
 * 输入的正整数个数为x
 * 1 <= x <= 1000
 * 输出
 * 最终栈中存留的元素值，元素值使用空格隔开，
 * 如8 7 6 5，栈顶数字在左边
 */
public class NewStackPollOrPush {

    public static void main (String[] args) {
        MyStack myStack = new MyStack(1000);
        myStack.push(1);
        myStack.push(2);
        myStack.push(5);
        myStack.push(7);
        myStack.push(9);
        myStack.push(1);
        myStack.push(2);
        myStack.push(2);

        while (myStack.size > 0){
            System.out.println(myStack.pol());
        }
    }

}
  class MyStack {
    int[] datas;
    int pushIndex;//入栈坐标
    int polIndex;//出栈坐标
    int size;

    public MyStack (int bigArray) {
        this.datas = new int[bigArray];
        this.pushIndex = 0;
        this.polIndex = 0;
        this.size = 0;
    }

    public void push (int input) {
        size++;
        if (size > datas.length) {
            size--;
            throw new RuntimeException("栈溢出");
        }

        datas[pushIndex] = input;
        polIndex = pushIndex;
        pushIndex = nextIndex(pushIndex);
        out:while (size > 1){
            int sum = 0;
            for (int i = pushIndex - 2; i >= 0; i--) {
                sum += datas[i];
                if (datas[size - 1] == sum){
                    int cacheindex = pushIndex;
                    for (int j = 0; j < cacheindex  - i; j++) {
                        pol();
                    }
                    datas[pushIndex ++] = 2 * sum;
                    polIndex++;
                    size ++;
                    continue out;
                }
            }
            break;
        }
    }

    public int pol () {
        if (size <= 0) {
            throw new RuntimeException("栈为空");
        }
        size--;
        int data = datas[polIndex];
        datas[polIndex] = 0;
        pushIndex = polIndex;
        polIndex = nextPullIndex(polIndex);
        return data;
    }

    private int nextPullIndex (int index) {
        return  --index;
    }

    private int nextIndex (int index) {
        return  ++index;
    }
}
